def insert_sort1(array):
    # 从第2个元素开始遍历数组array，记录当前遍历的元素的下标 i
    # 保存array[i]到temp里面
    # 确定array[i]插入的位置 考察的范围是 [0,i]
    # for(int j =0;j < i;j++)
    # if (array[j] < array[i]) j++
    # else break;
    # 找到了插入的位置 j
    ### 语义：变量j的语义是很明确的  #### 我们定义的所有变量都应该有它的语义，语义一定要明确！！
    # 先把 [j,i-1] 的元素整体往后移动一位
    # 再把array[i] 插入到 j 位置中: array[j] = array[i] (不对)
    # array[j] = temp
    ###

    for i in range(1, len(array)):
        temp = array[i]
        j = 0
        while j < i:
            if array[j] < array[i]:
                j += 1
            else:
                break
        # 找到了插入的位置 j
        # k = i-1
        # while k >= j:
        #     array[k+1] =array[k]
        #     k-=1
        for k in range(i - 1, j - 1, -1):
            array[k + 1] = array[k]

        array[j] = temp
    return array


def insert_sort2(array):
    # 模拟抓牌的过程
    for i in range(1, len(array)):

        # 确定array[i]在 [0,i-1] 里面的位置
        t = array[i]
        j = i
        while j > 0:
            if t < array[j - 1]:
                # 交换
                temp = array[j]
                array[j] = array[j - 1]
                array[j - 1] = temp
                j -= 1
            else:
                break
    return array


def insert_sort3(array):
    for i in range(1, len(array)):
        temp = array[i]
        j = i
        while j >= 0:
            if array[j - 1] > array[i]:
                j -= 1
            else:
                break
        if j == -1:
            j = 0
        k = i
        while k - 1 >= j:
            array[k] = array[k - 1]
            k -= 1
        array[j] = temp
    return array
